package Hot_100;

import java.util.Scanner;

//两数相加
public class Hot_100_2 {
    /**
     * 值域
     */
    public static class ListNode {
        int val;
        ListNode next;

        public ListNode(int x) {
            int val = x;
        }

        public ListNode(int x, ListNode next) {
            int val = x;
            this.next = next;
        }
    }

    /**
     * 主函数
     *
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ListNode l1 = new ListNode(-1);
        ListNode l2 = new ListNode(-1);
        System.out.print("请输入l1链表节点个数: ");
        int m = sc.nextInt();
        System.out.print("输入l1节点值: ");
        l1 = Create(m);
        System.out.print("结果: ");
        Print(l1);
        System.out.println();
        System.out.print("请输入l2链表节点个数: ");
        int n = sc.nextInt();
        System.out.print("输入l2节点值: ");
        l2 = Create(n);
        System.out.print("结果: ");
        Print(l2);
        System.out.println();
        System.out.println("l1、l2链表相加: ");
        ListNode l3 = new ListNode(-1);
        l3 = addTwoNumbers(l1, l2);
        System.out.print("结果: ");
        Print(l3);
    }

    /**
     * 创建链表函数
     *
     * @param n
     * @return
     */
    public static ListNode Create(int n) {
        Scanner sc = new Scanner(System.in);
        //定义投节点
        ListNode head = new ListNode(-1);
        ListNode p = head, q = head;
        //给头节点赋值
        p.val = sc.nextInt();
        n--;
        //依次赋值，形成链
        while (n > 0) {
            q = p;
            p = new ListNode(-1);
            p.val = sc.nextInt();
            q.next = p;
            n--;
        }
        return head;
    }

    /**
     * two sum函数
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 在两条链表上的指针
        ListNode p1 = l1, p2 = l2;
        // 虚拟头结点（构建新链表时的常用技巧）
        ListNode dummy = new ListNode(-1);
        // 指针 p 负责构建新链表
        ListNode p = dummy;
        // 记录进位
        int carry = 0;
        // 开始执行加法，两条链表走完且没有进位时才能结束循环
        while (p1 != null || p2 != null || carry > 0) {
            // 先加上上次的进位
            int val = carry;
            if (p1 != null) {
                val += p1.val;
                p1 = p1.next;
            }
            if (p2 != null) {
                val += p2.val;
                p2 = p2.next;
            }
            // 处理进位情况
            carry = val / 10;
            val = val % 10;
            // 构建新节点
            p.next = new ListNode(val);
            p = p.next;
        }
        // 返回结果链表的头结点（去除虚拟头结点）
        return dummy.next;
    }

    /**
     * 输出链表元素函数
     *
     * @param head
     */
    public static void Print(ListNode head) {
        for (ListNode p = head; p != null; p = p.next) {
            System.out.print(p.val + " ");
        }
    }
}
//时间复杂度: O(n)
//空间复杂度: O(n)